package com.java.multipledatasource.algorithm;

import org.apache.commons.lang3.StringUtils;

/**
 * @author hu
 * @version 1.0
 * @date 2021/1/22 0022 下午 1:16
 * @description 前缀树 以某个字符开始
 */
public class Trie {
    public static class Node1{
        private int pass;
        private int end;
        private Node1[] nexts;
        public Node1(){
            pass = 0;
            end = 0;
            //0 === a
            //1 === b
            //2 === c
            //…… ……
            //25 === z
            //nexts[i] === null i路径上不存在
            //nexts[i] != null i路径上存在
            nexts = new Node1[26];
        }
    }
    public static class Trie1{
        private Node1 root;
        public Trie1() {
            root = new Node1();
        }
        public void insert(String word){
            if (word != null) {
                Node1 node = root;
                node.pass++;
                char[] chars = word.toCharArray();
                int index = 0;
                for (char aChar : chars) {
                    index = aChar - 'a'; //有字符决定走那条路
                    if (node.nexts[index] == null) {
                        node.nexts[index] = new Node1();
                    }
                    node = node.nexts[index];
                    node.pass++;
                }
                node.end++;
            }
        }

        /**
         * 查询单词出现次数
         * @param word
         * @return
         */
        public int search(String word){
            if (StringUtils.isNotBlank(word)) {
                char[] chars = word.toCharArray();
                int index = 0;
                Node1 node = root;
                for (int i = 0; i < chars.length; i++) {
                    index = chars[i] - 'a';
                    if (node.nexts[index] == null) {
                        return 0;
                    }
                    node = node.nexts[index];
                }
                return node.end;
            }
            return 0;
        }

        /**
         * 以prefix开始的字符串有几个
         * @param prefix
         * @return
         */
        public int prefixNumber(String prefix){
            if (StringUtils.isNotBlank(prefix)) {
                Node1 node = root;
                int index = 0;
                char[] chars = prefix.toCharArray();
                for (char ch : chars) {
                    index = ch - 'a';
                    if (node.nexts[index] == null) {
                        return  0;
                    }
                    node = node.nexts[index];
                }
                return node.pass;
            }
            return  0;
        }

        /**
         * 删除某个节点
         * @param word
         */
        public void delete(String word){
            if (search(word) != 0) {
                Node1 node = root;
                int index ;
                char[] chars = word.toCharArray();
                for (char ch : chars) {
                    index = ch - 'a';
                    if (--node.nexts[index].pass == 0) {
                            node.nexts[index] = null;
                            return;
                    }
                    node = node.nexts[index];
                }
                node.end --;
            }
        }
    }


}
